//
// Created by 28735 on 2024/11/25.
//

#ifndef SELECTSORT_H
#define SELECTSORT_H

/*  选择排序分为简单选择排序和堆排序*/
inline void driectSort(int arr[])
{
    int length = sizeof(arr) / sizeof(int);
    for (int i = 0; i < length - 1; i++)
    {
        int temp = arr[i];
        int location = i;
        for (int j = i + 1; j < length; j++)
        {
            if (arr[j] > arr[i])
            {
                location = j;
            }
        }

        arr[i] = arr[location];
        arr[location] = temp;
    }
}


/*  大根堆*/
inline void heapAdjust(int arr[], int length)
{
    //如果是从1开始则是length/2
    int location = length/2 -1;
    for (int i = location; i >= 0; i--)
    {
        int j = i*2;
        if (j+1<length && arr[j+1] > arr[j])
        {
            j++;
        }

        if (arr[j] > arr[i])
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

inline void heapSort(int arr[])
{
    int length = sizeof(arr)/sizeof(int);

    heapAdjust(arr,length);

    for (int i = length; i > 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i-1];
        arr[i-1] = temp;

        heapAdjust(arr,i-1);
    }
}
#endif //SELECTSORT_H
